package leetCode.solution;

import java.util.Comparator;
import java.util.PriorityQueue;


public class Solution23 {
	
	public ListNode mergeKLists4(ListNode[] lists) {
		 if(lists==null || lists.length==0) {
			 return null;
		 }
		 return merge(lists,0,lists.length-1);
	 }
	
	private ListNode merge(ListNode[] lists, int left, int right) {
		int middle = left + ((right-left)>>1);
		if(left==right) return lists[left];
		if(left>right) return null;
		return mergeTwo(merge(lists,left,middle), merge(lists,middle+1,right));
	}
	
	
	 public ListNode mergeKLists1(ListNode[] lists) {
		 if(lists==null || lists.length==0) {
			 return null;
		 }
		 
		 ListNode ans = null;
		 for(ListNode node : lists) {
			 ans = mergeTwo(ans, node);
		 }
		 return ans;
	 }
	
	private ListNode mergeTwo(ListNode a, ListNode b) {
		
		if(a==null || b==null) {
			return a==null?b:a;
		}
		ListNode head = new ListNode();
		ListNode curr = head;
		
		while(a!=null &&b!=null) {
			if(a.val<b.val) {
				curr.next=a;
				a = a.next;
			}else {
				curr.next=b;
				b=b.next;
			}
			curr=curr.next;
		}
		curr.next = a==null?b:a;
		return head.next;
	}
	
    public ListNode mergeKLists2(ListNode[] lists) {
    	int index = 0;
    	ListNode curr = new ListNode(Integer.MAX_VALUE);
    	ListNode head = curr;
    	while(isNotEmpty(lists)) {
    		int minVal = Integer.MAX_VALUE;
    		for(int i=0;i<lists.length;i++) {
    			if(lists[i]==null) continue;
    			if(lists[i].val<=minVal) {
    				index = i;
    				minVal = lists[i].val;
    				curr.next = lists[i];
    			}
    		}
    		lists[index] = lists[index].next;
    		curr = curr.next;
    	}
    	return head.next;
    }
    
    private boolean isNotEmpty(ListNode[] lists) {
    	for(ListNode node : lists) {
    		if(node!=null) return true;
    	}
    	return false;
    }
    
    public ListNode mergeKLists3(ListNode[] lists) {

        if (lists.length == 0) {
            return null;
        }

        ListNode dummyHead = new ListNode(0);
        ListNode curr = dummyHead;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });

        for (ListNode list : lists) {
            if (list == null) {
                continue;
            }
            pq.add(list);
        }

        while (!pq.isEmpty()) {
            ListNode nextNode = pq.poll();
            curr.next = nextNode;
            curr = curr.next;
            if (nextNode.next != null) {
                pq.add(nextNode.next);
            }
        }
        return dummyHead.next;
    }
    
    public static void main(String[] args) {
		ListNode node1 = new ListNode(1);
		node1.next=new ListNode(4);
		node1.next.next=new ListNode(5);
		ListNode node2 = new ListNode(1);
		node2.next = new ListNode(3);
		node2.next.next = new ListNode(4);
		ListNode node3 = new ListNode(2);
		node3.next= new ListNode(6);
		
//		ListNode node = new Solution23().mergeKLists(new ListNode[] {node1,node2,node3});
//		while(node!=null) {
//			System.out.println(node.val);
//			node=node.next;
//		}
		ListNode node11 = new Solution23().mergeKLists4(new ListNode[] {node1,node2,node3});
		while(node11!=null) {
			System.out.println(node11.val);
			node11=node11.next;
		}
	}
    
    public static class ListNode {                                                     
        int val;                                                                
        ListNode next;                                                          
        ListNode() {}                                                           
        ListNode(int val) { this.val = val; }                                   
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }  
    }   
}